<!doctype html>

<html>
<head>
  <link rel="shortcut icon" href="static/images/favicon.ico" type="image/x-icon">
  <title>iter.js (Closure Library API Documentation - JavaScript)</title>
  <link rel="stylesheet" href="static/css/base.css">
  <link rel="stylesheet" href="static/css/doc.css">
  <link rel="stylesheet" href="static/css/sidetree.css">
  <link rel="stylesheet" href="static/css/prettify.css">

  <script>
     var _staticFilePath = "static/";
     var _typeTreeName = "goog";
     var _fileTreeName = "Source";
  </script>

  <script src="static/js/doc.js">
  </script>


  <meta charset="utf8">
</head>

<body onload="grokdoc.onLoad();">

<div id="header">
  <div class="g-section g-tpl-50-50 g-split">
    <div class="g-unit g-first">
      <a id="logo" href="index.html">Closure Library API Documentation</a>
    </div>

    <div class="g-unit">
      <div class="g-c">
        <strong>Go to class or file:</strong>
        <input type="text" id="ac">
      </div>
    </div>
  </div>
</div>

<div class="clear"></div>

<h2><a href="local_closure_goog_iter_iter.js.html">iter.js</a></h2>

<pre class="prettyprint lang-js">
<a name="line1"></a>// Copyright 2007 The Closure Library Authors. All Rights Reserved.
<a name="line2"></a>//
<a name="line3"></a>// Licensed under the Apache License, Version 2.0 (the &quot;License&quot;);
<a name="line4"></a>// you may not use this file except in compliance with the License.
<a name="line5"></a>// You may obtain a copy of the License at
<a name="line6"></a>//
<a name="line7"></a>//      http://www.apache.org/licenses/LICENSE-2.0
<a name="line8"></a>//
<a name="line9"></a>// Unless required by applicable law or agreed to in writing, software
<a name="line10"></a>// distributed under the License is distributed on an &quot;AS-IS&quot; BASIS,
<a name="line11"></a>// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
<a name="line12"></a>// See the License for the specific language governing permissions and
<a name="line13"></a>// limitations under the License.
<a name="line14"></a>
<a name="line15"></a>/**
<a name="line16"></a> * @fileoverview Python style iteration utilities.
<a name="line17"></a> * @author arv@google.com (Erik Arvidsson)
<a name="line18"></a> */
<a name="line19"></a>
<a name="line20"></a>
<a name="line21"></a>goog.provide(&#39;goog.iter&#39;);
<a name="line22"></a>goog.provide(&#39;goog.iter.Iterable&#39;);
<a name="line23"></a>goog.provide(&#39;goog.iter.Iterator&#39;);
<a name="line24"></a>goog.provide(&#39;goog.iter.StopIteration&#39;);
<a name="line25"></a>
<a name="line26"></a>goog.require(&#39;goog.array&#39;);
<a name="line27"></a>goog.require(&#39;goog.asserts&#39;);
<a name="line28"></a>goog.require(&#39;goog.functions&#39;);
<a name="line29"></a>goog.require(&#39;goog.math&#39;);
<a name="line30"></a>
<a name="line31"></a>
<a name="line32"></a>/**
<a name="line33"></a> * @typedef {goog.iter.Iterator|{length:number}|{__iterator__}}
<a name="line34"></a> */
<a name="line35"></a>goog.iter.Iterable;
<a name="line36"></a>
<a name="line37"></a>
<a name="line38"></a>// For script engines that already support iterators.
<a name="line39"></a>if (&#39;StopIteration&#39; in goog.global) {
<a name="line40"></a>  /**
<a name="line41"></a>   * Singleton Error object that is used to terminate iterations.
<a name="line42"></a>   * @type {Error}
<a name="line43"></a>   */
<a name="line44"></a>  goog.iter.StopIteration = goog.global[&#39;StopIteration&#39;];
<a name="line45"></a>} else {
<a name="line46"></a>  /**
<a name="line47"></a>   * Singleton Error object that is used to terminate iterations.
<a name="line48"></a>   * @type {Error}
<a name="line49"></a>   * @suppress {duplicate}
<a name="line50"></a>   */
<a name="line51"></a>  goog.iter.StopIteration = Error(&#39;StopIteration&#39;);
<a name="line52"></a>}
<a name="line53"></a>
<a name="line54"></a>
<a name="line55"></a>
<a name="line56"></a>/**
<a name="line57"></a> * Class/interface for iterators.  An iterator needs to implement a {@code next}
<a name="line58"></a> * method and it needs to throw a {@code goog.iter.StopIteration} when the
<a name="line59"></a> * iteration passes beyond the end.  Iterators have no {@code hasNext} method.
<a name="line60"></a> * It is recommended to always use the helper functions to iterate over the
<a name="line61"></a> * iterator or in case you are only targeting JavaScript 1.7 for in loops.
<a name="line62"></a> * @constructor
<a name="line63"></a> * @template VALUE
<a name="line64"></a> */
<a name="line65"></a>goog.iter.Iterator = function() {};
<a name="line66"></a>
<a name="line67"></a>
<a name="line68"></a>/**
<a name="line69"></a> * Returns the next value of the iteration.  This will throw the object
<a name="line70"></a> * {@see goog.iter#StopIteration} when the iteration passes the end.
<a name="line71"></a> * @return {VALUE} Any object or value.
<a name="line72"></a> */
<a name="line73"></a>goog.iter.Iterator.prototype.next = function() {
<a name="line74"></a>  throw goog.iter.StopIteration;
<a name="line75"></a>};
<a name="line76"></a>
<a name="line77"></a>
<a name="line78"></a>/**
<a name="line79"></a> * Returns the {@code Iterator} object itself.  This is used to implement
<a name="line80"></a> * the iterator protocol in JavaScript 1.7
<a name="line81"></a> * @param {boolean=} opt_keys  Whether to return the keys or values. Default is
<a name="line82"></a> *     to only return the values.  This is being used by the for-in loop (true)
<a name="line83"></a> *     and the for-each-in loop (false).  Even though the param gives a hint
<a name="line84"></a> *     about what the iterator will return there is no guarantee that it will
<a name="line85"></a> *     return the keys when true is passed.
<a name="line86"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} The object itself.
<a name="line87"></a> */
<a name="line88"></a>goog.iter.Iterator.prototype.__iterator__ = function(opt_keys) {
<a name="line89"></a>  return this;
<a name="line90"></a>};
<a name="line91"></a>
<a name="line92"></a>
<a name="line93"></a>/**
<a name="line94"></a> * Returns an iterator that knows how to iterate over the values in the object.
<a name="line95"></a> * @param {goog.iter.Iterator.&lt;VALUE&gt;|goog.iter.Iterable} iterable  If the
<a name="line96"></a> *     object is an iterator it will be returned as is.  If the object has an
<a name="line97"></a> *     {@code __iterator__} method that will be called to get the value
<a name="line98"></a> *     iterator.  If the object is an array-like object we create an iterator
<a name="line99"></a> *     for that.
<a name="line100"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} An iterator that knows how to iterate
<a name="line101"></a> *     over the values in {@code iterable}.
<a name="line102"></a> * @template VALUE
<a name="line103"></a> */
<a name="line104"></a>goog.iter.toIterator = function(iterable) {
<a name="line105"></a>  if (iterable instanceof goog.iter.Iterator) {
<a name="line106"></a>    return iterable;
<a name="line107"></a>  }
<a name="line108"></a>  if (typeof iterable.__iterator__ == &#39;function&#39;) {
<a name="line109"></a>    return iterable.__iterator__(false);
<a name="line110"></a>  }
<a name="line111"></a>  if (goog.isArrayLike(iterable)) {
<a name="line112"></a>    var i = 0;
<a name="line113"></a>    var newIter = new goog.iter.Iterator;
<a name="line114"></a>    newIter.next = function() {
<a name="line115"></a>      while (true) {
<a name="line116"></a>        if (i &gt;= iterable.length) {
<a name="line117"></a>          throw goog.iter.StopIteration;
<a name="line118"></a>        }
<a name="line119"></a>        // Don&#39;t include deleted elements.
<a name="line120"></a>        if (!(i in iterable)) {
<a name="line121"></a>          i++;
<a name="line122"></a>          continue;
<a name="line123"></a>        }
<a name="line124"></a>        return iterable[i++];
<a name="line125"></a>      }
<a name="line126"></a>    };
<a name="line127"></a>    return newIter;
<a name="line128"></a>  }
<a name="line129"></a>
<a name="line130"></a>
<a name="line131"></a>  // TODO(arv): Should we fall back on goog.structs.getValues()?
<a name="line132"></a>  throw Error(&#39;Not implemented&#39;);
<a name="line133"></a>};
<a name="line134"></a>
<a name="line135"></a>
<a name="line136"></a>/**
<a name="line137"></a> * Calls a function for each element in the iterator with the element of the
<a name="line138"></a> * iterator passed as argument.
<a name="line139"></a> *
<a name="line140"></a> * @param {goog.iter.Iterator.&lt;VALUE&gt;|goog.iter.Iterable} iterable  The iterator
<a name="line141"></a> *     to iterate over. If the iterable is an object {@code toIterator} will be
<a name="line142"></a> *     called on it.
<a name="line143"></a> * @param {function(this:THIS,VALUE,undefined,goog.iter.Iterator.&lt;VALUE&gt;)|
<a name="line144"></a> *         function(this:THIS,number,undefined,goog.iter.Iterator.&lt;VALUE&gt;)} f
<a name="line145"></a> *     The function to call for every element.  This function takes 3 arguments
<a name="line146"></a> *     (the element, undefined, and the iterator) and the return value is
<a name="line147"></a> *     irrelevant.  The reason for passing undefined as the second argument is
<a name="line148"></a> *     so that the same function can be used in {@see goog.array#forEach} as
<a name="line149"></a> *     well as others.
<a name="line150"></a> * @param {THIS=} opt_obj  The object to be used as the value of &#39;this&#39; within
<a name="line151"></a> *     {@code f}.
<a name="line152"></a> * @template THIS, VALUE
<a name="line153"></a> */
<a name="line154"></a>goog.iter.forEach = function(iterable, f, opt_obj) {
<a name="line155"></a>  if (goog.isArrayLike(iterable)) {
<a name="line156"></a>    /** @preserveTry */
<a name="line157"></a>    try {
<a name="line158"></a>      // NOTES: this passes the index number to the second parameter
<a name="line159"></a>      // of the callback contrary to the documentation above.
<a name="line160"></a>      goog.array.forEach(/** @type {goog.array.ArrayLike} */(iterable), f,
<a name="line161"></a>                         opt_obj);
<a name="line162"></a>    } catch (ex) {
<a name="line163"></a>      if (ex !== goog.iter.StopIteration) {
<a name="line164"></a>        throw ex;
<a name="line165"></a>      }
<a name="line166"></a>    }
<a name="line167"></a>  } else {
<a name="line168"></a>    iterable = goog.iter.toIterator(iterable);
<a name="line169"></a>    /** @preserveTry */
<a name="line170"></a>    try {
<a name="line171"></a>      while (true) {
<a name="line172"></a>        f.call(opt_obj, iterable.next(), undefined, iterable);
<a name="line173"></a>      }
<a name="line174"></a>    } catch (ex) {
<a name="line175"></a>      if (ex !== goog.iter.StopIteration) {
<a name="line176"></a>        throw ex;
<a name="line177"></a>      }
<a name="line178"></a>    }
<a name="line179"></a>  }
<a name="line180"></a>};
<a name="line181"></a>
<a name="line182"></a>
<a name="line183"></a>/**
<a name="line184"></a> * Calls a function for every element in the iterator, and if the function
<a name="line185"></a> * returns true adds the element to a new iterator.
<a name="line186"></a> *
<a name="line187"></a> * @param {goog.iter.Iterator.&lt;VALUE&gt;|goog.iter.Iterable} iterable The iterator
<a name="line188"></a> *     to iterate over.
<a name="line189"></a> * @param {
<a name="line190"></a> *     function(this:THIS,VALUE,undefined,goog.iter.Iterator.&lt;VALUE&gt;):boolean} f
<a name="line191"></a> *     The function to call for every element. This function takes 3 arguments
<a name="line192"></a> *     (the element, undefined, and the iterator) and should return a boolean.
<a name="line193"></a> *     If the return value is true the element will be included in the returned
<a name="line194"></a> *     iterator.  If it is false the element is not included.
<a name="line195"></a> * @param {THIS=} opt_obj The object to be used as the value of &#39;this&#39; within
<a name="line196"></a> *     {@code f}.
<a name="line197"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} A new iterator in which only elements
<a name="line198"></a> *     that passed the test are present.
<a name="line199"></a> * @template THIS, VALUE
<a name="line200"></a> */
<a name="line201"></a>goog.iter.filter = function(iterable, f, opt_obj) {
<a name="line202"></a>  var iterator = goog.iter.toIterator(iterable);
<a name="line203"></a>  var newIter = new goog.iter.Iterator;
<a name="line204"></a>  newIter.next = function() {
<a name="line205"></a>    while (true) {
<a name="line206"></a>      var val = iterator.next();
<a name="line207"></a>      if (f.call(opt_obj, val, undefined, iterator)) {
<a name="line208"></a>        return val;
<a name="line209"></a>      }
<a name="line210"></a>    }
<a name="line211"></a>  };
<a name="line212"></a>  return newIter;
<a name="line213"></a>};
<a name="line214"></a>
<a name="line215"></a>
<a name="line216"></a>/**
<a name="line217"></a> * Calls a function for every element in the iterator, and if the function
<a name="line218"></a> * returns false adds the element to a new iterator.
<a name="line219"></a> *
<a name="line220"></a> * @param {goog.iter.Iterator.&lt;VALUE&gt;|goog.iter.Iterable} iterable The iterator
<a name="line221"></a> *     to iterate over.
<a name="line222"></a> * @param {
<a name="line223"></a> *     function(this:THIS,VALUE,undefined,goog.iter.Iterator.&lt;VALUE&gt;):boolean} f
<a name="line224"></a> *     The function to call for every element. This function takes 3 arguments
<a name="line225"></a> *     (the element, undefined, and the iterator) and should return a boolean.
<a name="line226"></a> *     If the return value is false the element will be included in the returned
<a name="line227"></a> *     iterator.  If it is true the element is not included.
<a name="line228"></a> * @param {THIS=} opt_obj The object to be used as the value of &#39;this&#39; within
<a name="line229"></a> *     {@code f}.
<a name="line230"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} A new iterator in which only elements
<a name="line231"></a> *     that did not pass the test are present.
<a name="line232"></a> * @template THIS, VALUE
<a name="line233"></a> */
<a name="line234"></a>goog.iter.filterFalse = function(iterable, f, opt_obj) {
<a name="line235"></a>  return goog.iter.filter(iterable, goog.functions.not(f), opt_obj);
<a name="line236"></a>};
<a name="line237"></a>
<a name="line238"></a>
<a name="line239"></a>/**
<a name="line240"></a> * Creates a new iterator that returns the values in a range.  This function
<a name="line241"></a> * can take 1, 2 or 3 arguments:
<a name="line242"></a> * &lt;pre&gt;
<a name="line243"></a> * range(5) same as range(0, 5, 1)
<a name="line244"></a> * range(2, 5) same as range(2, 5, 1)
<a name="line245"></a> * &lt;/pre&gt;
<a name="line246"></a> *
<a name="line247"></a> * @param {number} startOrStop  The stop value if only one argument is provided.
<a name="line248"></a> *     The start value if 2 or more arguments are provided.  If only one
<a name="line249"></a> *     argument is used the start value is 0.
<a name="line250"></a> * @param {number=} opt_stop  The stop value.  If left out then the first
<a name="line251"></a> *     argument is used as the stop value.
<a name="line252"></a> * @param {number=} opt_step  The number to increment with between each call to
<a name="line253"></a> *     next.  This can be negative.
<a name="line254"></a> * @return {!goog.iter.Iterator.&lt;number&gt;} A new iterator that returns the values
<a name="line255"></a> *     in the range.
<a name="line256"></a> */
<a name="line257"></a>goog.iter.range = function(startOrStop, opt_stop, opt_step) {
<a name="line258"></a>  var start = 0;
<a name="line259"></a>  var stop = startOrStop;
<a name="line260"></a>  var step = opt_step || 1;
<a name="line261"></a>  if (arguments.length &gt; 1) {
<a name="line262"></a>    start = startOrStop;
<a name="line263"></a>    stop = opt_stop;
<a name="line264"></a>  }
<a name="line265"></a>  if (step == 0) {
<a name="line266"></a>    throw Error(&#39;Range step argument must not be zero&#39;);
<a name="line267"></a>  }
<a name="line268"></a>
<a name="line269"></a>  var newIter = new goog.iter.Iterator;
<a name="line270"></a>  newIter.next = function() {
<a name="line271"></a>    if (step &gt; 0 &amp;&amp; start &gt;= stop || step &lt; 0 &amp;&amp; start &lt;= stop) {
<a name="line272"></a>      throw goog.iter.StopIteration;
<a name="line273"></a>    }
<a name="line274"></a>    var rv = start;
<a name="line275"></a>    start += step;
<a name="line276"></a>    return rv;
<a name="line277"></a>  };
<a name="line278"></a>  return newIter;
<a name="line279"></a>};
<a name="line280"></a>
<a name="line281"></a>
<a name="line282"></a>/**
<a name="line283"></a> * Joins the values in a iterator with a delimiter.
<a name="line284"></a> * @param {goog.iter.Iterator.&lt;VALUE&gt;|goog.iter.Iterable} iterable The iterator
<a name="line285"></a> *     to get the values from.
<a name="line286"></a> * @param {string} deliminator  The text to put between the values.
<a name="line287"></a> * @return {string} The joined value string.
<a name="line288"></a> * @template VALUE
<a name="line289"></a> */
<a name="line290"></a>goog.iter.join = function(iterable, deliminator) {
<a name="line291"></a>  return goog.iter.toArray(iterable).join(deliminator);
<a name="line292"></a>};
<a name="line293"></a>
<a name="line294"></a>
<a name="line295"></a>/**
<a name="line296"></a> * For every element in the iterator call a function and return a new iterator
<a name="line297"></a> * with that value.
<a name="line298"></a> *
<a name="line299"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable The
<a name="line300"></a> *     iterator to iterate over.
<a name="line301"></a> * @param {
<a name="line302"></a> *     function(this:THIS,VALUE,undefined,!goog.iter.Iterator.&lt;VALUE&gt;):RESULT} f
<a name="line303"></a> *     The function to call for every element.  This function takes 3 arguments
<a name="line304"></a> *     (the element, undefined, and the iterator) and should return a new value.
<a name="line305"></a> * @param {THIS=} opt_obj The object to be used as the value of &#39;this&#39; within
<a name="line306"></a> *     {@code f}.
<a name="line307"></a> * @return {!goog.iter.Iterator.&lt;RESULT&gt;} A new iterator that returns the
<a name="line308"></a> *     results of applying the function to each element in the original
<a name="line309"></a> *     iterator.
<a name="line310"></a> * @template THIS, VALUE, RESULT
<a name="line311"></a> */
<a name="line312"></a>goog.iter.map = function(iterable, f, opt_obj) {
<a name="line313"></a>  var iterator = goog.iter.toIterator(iterable);
<a name="line314"></a>  var newIter = new goog.iter.Iterator;
<a name="line315"></a>  newIter.next = function() {
<a name="line316"></a>    var val = iterator.next();
<a name="line317"></a>    return f.call(opt_obj, val, undefined, iterator);
<a name="line318"></a>  };
<a name="line319"></a>  return newIter;
<a name="line320"></a>};
<a name="line321"></a>
<a name="line322"></a>
<a name="line323"></a>/**
<a name="line324"></a> * Passes every element of an iterator into a function and accumulates the
<a name="line325"></a> * result.
<a name="line326"></a> *
<a name="line327"></a> * @param {goog.iter.Iterator.&lt;VALUE&gt;|goog.iter.Iterable} iterable The iterator
<a name="line328"></a> *     to iterate over.
<a name="line329"></a> * @param {function(this:THIS,VALUE,VALUE):VALUE} f The function to call for
<a name="line330"></a> *     every element. This function takes 2 arguments (the function&#39;s previous
<a name="line331"></a> *     result or the initial value, and the value of the current element).
<a name="line332"></a> *     function(previousValue, currentElement) : newValue.
<a name="line333"></a> * @param {VALUE} val The initial value to pass into the function on the first
<a name="line334"></a> *     call.
<a name="line335"></a> * @param {THIS=} opt_obj  The object to be used as the value of &#39;this&#39; within
<a name="line336"></a> *     f.
<a name="line337"></a> * @return {VALUE} Result of evaluating f repeatedly across the values of
<a name="line338"></a> *     the iterator.
<a name="line339"></a> * @template THIS, VALUE
<a name="line340"></a> */
<a name="line341"></a>goog.iter.reduce = function(iterable, f, val, opt_obj) {
<a name="line342"></a>  var rval = val;
<a name="line343"></a>  goog.iter.forEach(iterable, function(val) {
<a name="line344"></a>    rval = f.call(opt_obj, rval, val);
<a name="line345"></a>  });
<a name="line346"></a>  return rval;
<a name="line347"></a>};
<a name="line348"></a>
<a name="line349"></a>
<a name="line350"></a>/**
<a name="line351"></a> * Goes through the values in the iterator. Calls f for each of these, and if
<a name="line352"></a> * any of them returns true, this returns true (without checking the rest). If
<a name="line353"></a> * all return false this will return false.
<a name="line354"></a> *
<a name="line355"></a> * @param {goog.iter.Iterator.&lt;VALUE&gt;|goog.iter.Iterable} iterable The iterator
<a name="line356"></a> *     object.
<a name="line357"></a> * @param {
<a name="line358"></a> *     function(this:THIS,VALUE,undefined,goog.iter.Iterator.&lt;VALUE&gt;):boolean} f
<a name="line359"></a> *     The function to call for every value. This function takes 3 arguments
<a name="line360"></a> *     (the value, undefined, and the iterator) and should return a boolean.
<a name="line361"></a> * @param {THIS=} opt_obj The object to be used as the value of &#39;this&#39; within
<a name="line362"></a> *     {@code f}.
<a name="line363"></a> * @return {boolean} true if any value passes the test.
<a name="line364"></a> * @template THIS, VALUE
<a name="line365"></a> */
<a name="line366"></a>goog.iter.some = function(iterable, f, opt_obj) {
<a name="line367"></a>  iterable = goog.iter.toIterator(iterable);
<a name="line368"></a>  /** @preserveTry */
<a name="line369"></a>  try {
<a name="line370"></a>    while (true) {
<a name="line371"></a>      if (f.call(opt_obj, iterable.next(), undefined, iterable)) {
<a name="line372"></a>        return true;
<a name="line373"></a>      }
<a name="line374"></a>    }
<a name="line375"></a>  } catch (ex) {
<a name="line376"></a>    if (ex !== goog.iter.StopIteration) {
<a name="line377"></a>      throw ex;
<a name="line378"></a>    }
<a name="line379"></a>  }
<a name="line380"></a>  return false;
<a name="line381"></a>};
<a name="line382"></a>
<a name="line383"></a>
<a name="line384"></a>/**
<a name="line385"></a> * Goes through the values in the iterator. Calls f for each of these and if any
<a name="line386"></a> * of them returns false this returns false (without checking the rest). If all
<a name="line387"></a> * return true this will return true.
<a name="line388"></a> *
<a name="line389"></a> * @param {goog.iter.Iterator.&lt;VALUE&gt;|goog.iter.Iterable} iterable The iterator
<a name="line390"></a> *     object.
<a name="line391"></a> * @param {
<a name="line392"></a> *     function(this:THIS,VALUE,undefined,goog.iter.Iterator.&lt;VALUE&gt;):boolean} f
<a name="line393"></a> *     The function to call for every value. This function takes 3 arguments
<a name="line394"></a> *     (the value, undefined, and the iterator) and should return a boolean.
<a name="line395"></a> * @param {THIS=} opt_obj The object to be used as the value of &#39;this&#39; within
<a name="line396"></a> *     {@code f}.
<a name="line397"></a> * @return {boolean} true if every value passes the test.
<a name="line398"></a> * @template THIS, VALUE
<a name="line399"></a> */
<a name="line400"></a>goog.iter.every = function(iterable, f, opt_obj) {
<a name="line401"></a>  iterable = goog.iter.toIterator(iterable);
<a name="line402"></a>  /** @preserveTry */
<a name="line403"></a>  try {
<a name="line404"></a>    while (true) {
<a name="line405"></a>      if (!f.call(opt_obj, iterable.next(), undefined, iterable)) {
<a name="line406"></a>        return false;
<a name="line407"></a>      }
<a name="line408"></a>    }
<a name="line409"></a>  } catch (ex) {
<a name="line410"></a>    if (ex !== goog.iter.StopIteration) {
<a name="line411"></a>      throw ex;
<a name="line412"></a>    }
<a name="line413"></a>  }
<a name="line414"></a>  return true;
<a name="line415"></a>};
<a name="line416"></a>
<a name="line417"></a>
<a name="line418"></a>/**
<a name="line419"></a> * Takes zero or more iterables and returns one iterator that will iterate over
<a name="line420"></a> * them in the order chained.
<a name="line421"></a> * @param {...!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} var_args Any
<a name="line422"></a> *     number of iterable objects.
<a name="line423"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} Returns a new iterator that will
<a name="line424"></a> *     iterate over all the given iterables&#39; contents.
<a name="line425"></a> * @template VALUE
<a name="line426"></a> */
<a name="line427"></a>goog.iter.chain = function(var_args) {
<a name="line428"></a>  var iterator = goog.iter.toIterator(arguments);
<a name="line429"></a>  var iter = new goog.iter.Iterator();
<a name="line430"></a>  var current = null;
<a name="line431"></a>
<a name="line432"></a>  iter.next = function() {
<a name="line433"></a>    while (true) {
<a name="line434"></a>      if (current == null) {
<a name="line435"></a>        var it = iterator.next();
<a name="line436"></a>        current = goog.iter.toIterator(it);
<a name="line437"></a>      }
<a name="line438"></a>      try {
<a name="line439"></a>        return current.next();
<a name="line440"></a>      } catch (ex) {
<a name="line441"></a>        if (ex !== goog.iter.StopIteration) {
<a name="line442"></a>          throw ex;
<a name="line443"></a>        }
<a name="line444"></a>        current = null;
<a name="line445"></a>      }
<a name="line446"></a>    }
<a name="line447"></a>  };
<a name="line448"></a>
<a name="line449"></a>  return iter;
<a name="line450"></a>};
<a name="line451"></a>
<a name="line452"></a>
<a name="line453"></a>/**
<a name="line454"></a> * Takes a single iterable containing zero or more iterables and returns one
<a name="line455"></a> * iterator that will iterate over each one in the order given.
<a name="line456"></a> * @see http://docs.python.org/2/library/itertools.html#itertools.chain.from_iterable
<a name="line457"></a> * @param {goog.iter.Iterable} iterable The iterable of iterables to chain.
<a name="line458"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} Returns a new iterator that will
<a name="line459"></a> *     iterate over all the contents of the iterables contained within
<a name="line460"></a> *     {@code iterable}.
<a name="line461"></a> * @template VALUE
<a name="line462"></a> */
<a name="line463"></a>goog.iter.chainFromIterable = function(iterable) {
<a name="line464"></a>  return goog.iter.chain.apply(undefined, iterable);
<a name="line465"></a>};
<a name="line466"></a>
<a name="line467"></a>
<a name="line468"></a>/**
<a name="line469"></a> * Builds a new iterator that iterates over the original, but skips elements as
<a name="line470"></a> * long as a supplied function returns true.
<a name="line471"></a> * @param {goog.iter.Iterator.&lt;VALUE&gt;|goog.iter.Iterable} iterable The iterator
<a name="line472"></a> *     object.
<a name="line473"></a> * @param {
<a name="line474"></a> *     function(this:THIS,VALUE,undefined,goog.iter.Iterator.&lt;VALUE&gt;):boolean} f
<a name="line475"></a> *     The function to call for every value. This function takes 3 arguments
<a name="line476"></a> *     (the value, undefined, and the iterator) and should return a boolean.
<a name="line477"></a> * @param {THIS=} opt_obj The object to be used as the value of &#39;this&#39; within
<a name="line478"></a> *     {@code f}.
<a name="line479"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} A new iterator that drops elements from
<a name="line480"></a> *     the original iterator as long as {@code f} is true.
<a name="line481"></a> * @template THIS, VALUE
<a name="line482"></a> */
<a name="line483"></a>goog.iter.dropWhile = function(iterable, f, opt_obj) {
<a name="line484"></a>  var iterator = goog.iter.toIterator(iterable);
<a name="line485"></a>  var newIter = new goog.iter.Iterator;
<a name="line486"></a>  var dropping = true;
<a name="line487"></a>  newIter.next = function() {
<a name="line488"></a>    while (true) {
<a name="line489"></a>      var val = iterator.next();
<a name="line490"></a>      if (dropping &amp;&amp; f.call(opt_obj, val, undefined, iterator)) {
<a name="line491"></a>        continue;
<a name="line492"></a>      } else {
<a name="line493"></a>        dropping = false;
<a name="line494"></a>      }
<a name="line495"></a>      return val;
<a name="line496"></a>    }
<a name="line497"></a>  };
<a name="line498"></a>  return newIter;
<a name="line499"></a>};
<a name="line500"></a>
<a name="line501"></a>
<a name="line502"></a>/**
<a name="line503"></a> * Builds a new iterator that iterates over the original, but only as long as a
<a name="line504"></a> * supplied function returns true.
<a name="line505"></a> * @param {goog.iter.Iterator.&lt;VALUE&gt;|goog.iter.Iterable} iterable The iterator
<a name="line506"></a> *     object.
<a name="line507"></a> * @param {
<a name="line508"></a> *     function(this:THIS,VALUE,undefined,goog.iter.Iterator.&lt;VALUE&gt;):boolean} f
<a name="line509"></a> *     The function to call for every value. This function takes 3 arguments
<a name="line510"></a> *     (the value, undefined, and the iterator) and should return a boolean.
<a name="line511"></a> * @param {THIS=} opt_obj This is used as the &#39;this&#39; object in f when called.
<a name="line512"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} A new iterator that keeps elements in
<a name="line513"></a> *     the original iterator as long as the function is true.
<a name="line514"></a> * @template THIS, VALUE
<a name="line515"></a> */
<a name="line516"></a>goog.iter.takeWhile = function(iterable, f, opt_obj) {
<a name="line517"></a>  var iterator = goog.iter.toIterator(iterable);
<a name="line518"></a>  var newIter = new goog.iter.Iterator;
<a name="line519"></a>  var taking = true;
<a name="line520"></a>  newIter.next = function() {
<a name="line521"></a>    while (true) {
<a name="line522"></a>      if (taking) {
<a name="line523"></a>        var val = iterator.next();
<a name="line524"></a>        if (f.call(opt_obj, val, undefined, iterator)) {
<a name="line525"></a>          return val;
<a name="line526"></a>        } else {
<a name="line527"></a>          taking = false;
<a name="line528"></a>        }
<a name="line529"></a>      } else {
<a name="line530"></a>        throw goog.iter.StopIteration;
<a name="line531"></a>      }
<a name="line532"></a>    }
<a name="line533"></a>  };
<a name="line534"></a>  return newIter;
<a name="line535"></a>};
<a name="line536"></a>
<a name="line537"></a>
<a name="line538"></a>/**
<a name="line539"></a> * Converts the iterator to an array
<a name="line540"></a> * @param {goog.iter.Iterator.&lt;VALUE&gt;|goog.iter.Iterable} iterable The iterator
<a name="line541"></a> *     to convert to an array.
<a name="line542"></a> * @return {!Array.&lt;VALUE&gt;} An array of the elements the iterator iterates over.
<a name="line543"></a> * @template VALUE
<a name="line544"></a> */
<a name="line545"></a>goog.iter.toArray = function(iterable) {
<a name="line546"></a>  // Fast path for array-like.
<a name="line547"></a>  if (goog.isArrayLike(iterable)) {
<a name="line548"></a>    return goog.array.toArray(/** @type {!goog.array.ArrayLike} */(iterable));
<a name="line549"></a>  }
<a name="line550"></a>  iterable = goog.iter.toIterator(iterable);
<a name="line551"></a>  var array = [];
<a name="line552"></a>  goog.iter.forEach(iterable, function(val) {
<a name="line553"></a>    array.push(val);
<a name="line554"></a>  });
<a name="line555"></a>  return array;
<a name="line556"></a>};
<a name="line557"></a>
<a name="line558"></a>
<a name="line559"></a>/**
<a name="line560"></a> * Iterates over two iterables and returns true if they contain the same
<a name="line561"></a> * sequence of elements and have the same length.
<a name="line562"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable1 The first
<a name="line563"></a> *     iterable object.
<a name="line564"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable2 The second
<a name="line565"></a> *     iterable object.
<a name="line566"></a> * @return {boolean} true if the iterables contain the same sequence of elements
<a name="line567"></a> *     and have the same length.
<a name="line568"></a> * @template VALUE
<a name="line569"></a> */
<a name="line570"></a>goog.iter.equals = function(iterable1, iterable2) {
<a name="line571"></a>  var fillValue = {};
<a name="line572"></a>  var pairs = goog.iter.zipLongest(fillValue, iterable1, iterable2);
<a name="line573"></a>  return goog.iter.every(pairs, function(pair) {
<a name="line574"></a>    return pair[0] == pair[1];
<a name="line575"></a>  });
<a name="line576"></a>};
<a name="line577"></a>
<a name="line578"></a>
<a name="line579"></a>/**
<a name="line580"></a> * Advances the iterator to the next position, returning the given default value
<a name="line581"></a> * instead of throwing an exception if the iterator has no more entries.
<a name="line582"></a> * @param {goog.iter.Iterator.&lt;VALUE&gt;|goog.iter.Iterable} iterable The iterable
<a name="line583"></a> *     object.
<a name="line584"></a> * @param {VALUE} defaultValue The value to return if the iterator is empty.
<a name="line585"></a> * @return {VALUE} The next item in the iteration, or defaultValue if the
<a name="line586"></a> *     iterator was empty.
<a name="line587"></a> * @template VALUE
<a name="line588"></a> */
<a name="line589"></a>goog.iter.nextOrValue = function(iterable, defaultValue) {
<a name="line590"></a>  try {
<a name="line591"></a>    return goog.iter.toIterator(iterable).next();
<a name="line592"></a>  } catch (e) {
<a name="line593"></a>    if (e != goog.iter.StopIteration) {
<a name="line594"></a>      throw e;
<a name="line595"></a>    }
<a name="line596"></a>    return defaultValue;
<a name="line597"></a>  }
<a name="line598"></a>};
<a name="line599"></a>
<a name="line600"></a>
<a name="line601"></a>/**
<a name="line602"></a> * Cartesian product of zero or more sets.  Gives an iterator that gives every
<a name="line603"></a> * combination of one element chosen from each set.  For example,
<a name="line604"></a> * ([1, 2], [3, 4]) gives ([1, 3], [1, 4], [2, 3], [2, 4]).
<a name="line605"></a> * @see http://docs.python.org/library/itertools.html#itertools.product
<a name="line606"></a> * @param {...!goog.array.ArrayLike.&lt;VALUE&gt;} var_args Zero or more sets, as
<a name="line607"></a> *     arrays.
<a name="line608"></a> * @return {!goog.iter.Iterator.&lt;!Array.&lt;VALUE&gt;&gt;} An iterator that gives each
<a name="line609"></a> *     n-tuple (as an array).
<a name="line610"></a> * @template VALUE
<a name="line611"></a> */
<a name="line612"></a>goog.iter.product = function(var_args) {
<a name="line613"></a>  var someArrayEmpty = goog.array.some(arguments, function(arr) {
<a name="line614"></a>    return !arr.length;
<a name="line615"></a>  });
<a name="line616"></a>
<a name="line617"></a>  // An empty set in a cartesian product gives an empty set.
<a name="line618"></a>  if (someArrayEmpty || !arguments.length) {
<a name="line619"></a>    return new goog.iter.Iterator();
<a name="line620"></a>  }
<a name="line621"></a>
<a name="line622"></a>  var iter = new goog.iter.Iterator();
<a name="line623"></a>  var arrays = arguments;
<a name="line624"></a>
<a name="line625"></a>  // The first indices are [0, 0, ...]
<a name="line626"></a>  var indicies = goog.array.repeat(0, arrays.length);
<a name="line627"></a>
<a name="line628"></a>  iter.next = function() {
<a name="line629"></a>
<a name="line630"></a>    if (indicies) {
<a name="line631"></a>      var retVal = goog.array.map(indicies, function(valueIndex, arrayIndex) {
<a name="line632"></a>        return arrays[arrayIndex][valueIndex];
<a name="line633"></a>      });
<a name="line634"></a>
<a name="line635"></a>      // Generate the next-largest indices for the next call.
<a name="line636"></a>      // Increase the rightmost index. If it goes over, increase the next
<a name="line637"></a>      // rightmost (like carry-over addition).
<a name="line638"></a>      for (var i = indicies.length - 1; i &gt;= 0; i--) {
<a name="line639"></a>        // Assertion prevents compiler warning below.
<a name="line640"></a>        goog.asserts.assert(indicies);
<a name="line641"></a>        if (indicies[i] &lt; arrays[i].length - 1) {
<a name="line642"></a>          indicies[i]++;
<a name="line643"></a>          break;
<a name="line644"></a>        }
<a name="line645"></a>
<a name="line646"></a>        // We&#39;re at the last indices (the last element of every array), so
<a name="line647"></a>        // the iteration is over on the next call.
<a name="line648"></a>        if (i == 0) {
<a name="line649"></a>          indicies = null;
<a name="line650"></a>          break;
<a name="line651"></a>        }
<a name="line652"></a>        // Reset the index in this column and loop back to increment the
<a name="line653"></a>        // next one.
<a name="line654"></a>        indicies[i] = 0;
<a name="line655"></a>      }
<a name="line656"></a>      return retVal;
<a name="line657"></a>    }
<a name="line658"></a>
<a name="line659"></a>    throw goog.iter.StopIteration;
<a name="line660"></a>  };
<a name="line661"></a>
<a name="line662"></a>  return iter;
<a name="line663"></a>};
<a name="line664"></a>
<a name="line665"></a>
<a name="line666"></a>/**
<a name="line667"></a> * Create an iterator to cycle over the iterable&#39;s elements indefinitely.
<a name="line668"></a> * For example, ([1, 2, 3]) would return : 1, 2, 3, 1, 2, 3, ...
<a name="line669"></a> * @see: http://docs.python.org/library/itertools.html#itertools.cycle.
<a name="line670"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable The
<a name="line671"></a> *     iterable object.
<a name="line672"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} An iterator that iterates indefinitely
<a name="line673"></a> *     over the values in {@code iterable}.
<a name="line674"></a> * @template VALUE
<a name="line675"></a> */
<a name="line676"></a>goog.iter.cycle = function(iterable) {
<a name="line677"></a>  var baseIterator = goog.iter.toIterator(iterable);
<a name="line678"></a>
<a name="line679"></a>  // We maintain a cache to store the iterable elements as we iterate
<a name="line680"></a>  // over them. The cache is used to return elements once we have
<a name="line681"></a>  // iterated over the iterable once.
<a name="line682"></a>  var cache = [];
<a name="line683"></a>  var cacheIndex = 0;
<a name="line684"></a>
<a name="line685"></a>  var iter = new goog.iter.Iterator();
<a name="line686"></a>
<a name="line687"></a>  // This flag is set after the iterable is iterated over once
<a name="line688"></a>  var useCache = false;
<a name="line689"></a>
<a name="line690"></a>  iter.next = function() {
<a name="line691"></a>    var returnElement = null;
<a name="line692"></a>
<a name="line693"></a>    // Pull elements off the original iterator if not using cache
<a name="line694"></a>    if (!useCache) {
<a name="line695"></a>      try {
<a name="line696"></a>        // Return the element from the iterable
<a name="line697"></a>        returnElement = baseIterator.next();
<a name="line698"></a>        cache.push(returnElement);
<a name="line699"></a>        return returnElement;
<a name="line700"></a>      } catch (e) {
<a name="line701"></a>        // If an exception other than StopIteration is thrown
<a name="line702"></a>        // or if there are no elements to iterate over (the iterable was empty)
<a name="line703"></a>        // throw an exception
<a name="line704"></a>        if (e != goog.iter.StopIteration || goog.array.isEmpty(cache)) {
<a name="line705"></a>          throw e;
<a name="line706"></a>        }
<a name="line707"></a>        // set useCache to true after we know that a &#39;StopIteration&#39; exception
<a name="line708"></a>        // was thrown and the cache is not empty (to handle the &#39;empty iterable&#39;
<a name="line709"></a>        // use case)
<a name="line710"></a>        useCache = true;
<a name="line711"></a>      }
<a name="line712"></a>    }
<a name="line713"></a>
<a name="line714"></a>    returnElement = cache[cacheIndex];
<a name="line715"></a>    cacheIndex = (cacheIndex + 1) % cache.length;
<a name="line716"></a>
<a name="line717"></a>    return returnElement;
<a name="line718"></a>  };
<a name="line719"></a>
<a name="line720"></a>  return iter;
<a name="line721"></a>};
<a name="line722"></a>
<a name="line723"></a>
<a name="line724"></a>/**
<a name="line725"></a> * Creates an iterator that counts indefinitely from a starting value.
<a name="line726"></a> * @see http://docs.python.org/2/library/itertools.html#itertools.count
<a name="line727"></a> * @param {number=} opt_start The starting value. Default is 0.
<a name="line728"></a> * @param {number=} opt_step The number to increment with between each call to
<a name="line729"></a> *     next. Negative and floating point numbers are allowed. Default is 1.
<a name="line730"></a> * @return {!goog.iter.Iterator.&lt;number&gt;} A new iterator that returns the values
<a name="line731"></a> *     in the series.
<a name="line732"></a> */
<a name="line733"></a>goog.iter.count = function(opt_start, opt_step) {
<a name="line734"></a>  var counter = opt_start || 0;
<a name="line735"></a>  var step = goog.isDef(opt_step) ? opt_step : 1;
<a name="line736"></a>  var iter = new goog.iter.Iterator();
<a name="line737"></a>
<a name="line738"></a>  iter.next = function() {
<a name="line739"></a>    var returnValue = counter;
<a name="line740"></a>    counter += step;
<a name="line741"></a>    return returnValue;
<a name="line742"></a>  };
<a name="line743"></a>
<a name="line744"></a>  return iter;
<a name="line745"></a>};
<a name="line746"></a>
<a name="line747"></a>
<a name="line748"></a>/**
<a name="line749"></a> * Creates an iterator that returns the same object or value repeatedly.
<a name="line750"></a> * @param {VALUE} value Any object or value to repeat.
<a name="line751"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} A new iterator that returns the
<a name="line752"></a> *     repeated value.
<a name="line753"></a> * @template VALUE
<a name="line754"></a> */
<a name="line755"></a>goog.iter.repeat = function(value) {
<a name="line756"></a>  var iter = new goog.iter.Iterator();
<a name="line757"></a>
<a name="line758"></a>  iter.next = goog.functions.constant(value);
<a name="line759"></a>
<a name="line760"></a>  return iter;
<a name="line761"></a>};
<a name="line762"></a>
<a name="line763"></a>
<a name="line764"></a>/**
<a name="line765"></a> * Creates an iterator that returns running totals from the numbers in
<a name="line766"></a> * {@code iterable}. For example, the array {@code [1, 2, 3, 4, 5]} yields
<a name="line767"></a> * {@code 1 -&gt; 3 -&gt; 6 -&gt; 10 -&gt; 15}.
<a name="line768"></a> * @see http://docs.python.org/3.2/library/itertools.html#itertools.accumulate
<a name="line769"></a> * @param {!goog.iter.Iterable.&lt;number&gt;} iterable The iterable of numbers to
<a name="line770"></a> *     accumulate.
<a name="line771"></a> * @return {!goog.iter.Iterator.&lt;number&gt;} A new iterator that returns the
<a name="line772"></a> *     numbers in the series.
<a name="line773"></a> */
<a name="line774"></a>goog.iter.accumulate = function(iterable) {
<a name="line775"></a>  var iterator = goog.iter.toIterator(iterable);
<a name="line776"></a>  var total = 0;
<a name="line777"></a>  var iter = new goog.iter.Iterator();
<a name="line778"></a>
<a name="line779"></a>  iter.next = function() {
<a name="line780"></a>    total += iterator.next();
<a name="line781"></a>    return total;
<a name="line782"></a>  };
<a name="line783"></a>
<a name="line784"></a>  return iter;
<a name="line785"></a>};
<a name="line786"></a>
<a name="line787"></a>
<a name="line788"></a>/**
<a name="line789"></a> * Creates an iterator that returns arrays containing the ith elements from the
<a name="line790"></a> * provided iterables. The returned arrays will be the same size as the number
<a name="line791"></a> * of iterables given in {@code var_args}. Once the shortest iterable is
<a name="line792"></a> * exhausted, subsequent calls to {@code next()} will throw
<a name="line793"></a> * {@code goog.iter.StopIteration}.
<a name="line794"></a> * @see http://docs.python.org/2/library/itertools.html#itertools.izip
<a name="line795"></a> * @param {...!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} var_args Any
<a name="line796"></a> *     number of iterable objects.
<a name="line797"></a> * @return {!goog.iter.Iterator.&lt;!Array.&lt;VALUE&gt;&gt;} A new iterator that returns
<a name="line798"></a> *     arrays of elements from the provided iterables.
<a name="line799"></a> * @template VALUE
<a name="line800"></a> */
<a name="line801"></a>goog.iter.zip = function(var_args) {
<a name="line802"></a>  var args = arguments;
<a name="line803"></a>  var iter = new goog.iter.Iterator();
<a name="line804"></a>
<a name="line805"></a>  if (args.length &gt; 0) {
<a name="line806"></a>    var iterators = goog.array.map(args, goog.iter.toIterator);
<a name="line807"></a>    iter.next = function() {
<a name="line808"></a>      var arr = goog.array.map(iterators, function(it) {
<a name="line809"></a>        return it.next();
<a name="line810"></a>      });
<a name="line811"></a>      return arr;
<a name="line812"></a>    };
<a name="line813"></a>  }
<a name="line814"></a>
<a name="line815"></a>  return iter;
<a name="line816"></a>};
<a name="line817"></a>
<a name="line818"></a>
<a name="line819"></a>/**
<a name="line820"></a> * Creates an iterator that returns arrays containing the ith elements from the
<a name="line821"></a> * provided iterables. The returned arrays will be the same size as the number
<a name="line822"></a> * of iterables given in {@code var_args}. Shorter iterables will be extended
<a name="line823"></a> * with {@code fillValue}. Once the longest iterable is exhausted, subsequent
<a name="line824"></a> * calls to {@code next()} will throw {@code goog.iter.StopIteration}.
<a name="line825"></a> * @see http://docs.python.org/2/library/itertools.html#itertools.izip_longest
<a name="line826"></a> * @param {VALUE} fillValue The object or value used to fill shorter iterables.
<a name="line827"></a> * @param {...!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} var_args Any
<a name="line828"></a> *     number of iterable objects.
<a name="line829"></a> * @return {!goog.iter.Iterator.&lt;!Array.&lt;VALUE&gt;&gt;} A new iterator that returns
<a name="line830"></a> *     arrays of elements from the provided iterables.
<a name="line831"></a> * @template VALUE
<a name="line832"></a> */
<a name="line833"></a>goog.iter.zipLongest = function(fillValue, var_args) {
<a name="line834"></a>  var args = goog.array.slice(arguments, 1);
<a name="line835"></a>  var iter = new goog.iter.Iterator();
<a name="line836"></a>
<a name="line837"></a>  if (args.length &gt; 0) {
<a name="line838"></a>    var iterators = goog.array.map(args, goog.iter.toIterator);
<a name="line839"></a>
<a name="line840"></a>    iter.next = function() {
<a name="line841"></a>      var iteratorsHaveValues = false;  // false when all iterators are empty.
<a name="line842"></a>      var arr = goog.array.map(iterators, function(it) {
<a name="line843"></a>        var returnValue;
<a name="line844"></a>        try {
<a name="line845"></a>          returnValue = it.next();
<a name="line846"></a>          // Iterator had a value, so we&#39;ve not exhausted the iterators.
<a name="line847"></a>          // Set flag accordingly.
<a name="line848"></a>          iteratorsHaveValues = true;
<a name="line849"></a>        } catch (ex) {
<a name="line850"></a>          if (ex !== goog.iter.StopIteration) {
<a name="line851"></a>            throw ex;
<a name="line852"></a>          }
<a name="line853"></a>          returnValue = fillValue;
<a name="line854"></a>        }
<a name="line855"></a>        return returnValue;
<a name="line856"></a>      });
<a name="line857"></a>
<a name="line858"></a>      if (!iteratorsHaveValues) {
<a name="line859"></a>        throw goog.iter.StopIteration;
<a name="line860"></a>      }
<a name="line861"></a>      return arr;
<a name="line862"></a>    };
<a name="line863"></a>  }
<a name="line864"></a>
<a name="line865"></a>  return iter;
<a name="line866"></a>};
<a name="line867"></a>
<a name="line868"></a>
<a name="line869"></a>/**
<a name="line870"></a> * Creates an iterator that filters {@code iterable} based on a series of
<a name="line871"></a> * {@code selectors}. On each call to {@code next()}, one item is taken from
<a name="line872"></a> * both the {@code iterable} and {@code selectors} iterators. If the item from
<a name="line873"></a> * {@code selectors} evaluates to true, the item from {@code iterable} is given.
<a name="line874"></a> * Otherwise, it is skipped. Once either {@code iterable} or {@code selectors}
<a name="line875"></a> * is exhausted, subsequent calls to {@code next()} will throw
<a name="line876"></a> * {@code goog.iter.StopIteration}.
<a name="line877"></a> * @see http://docs.python.org/2/library/itertools.html#itertools.compress
<a name="line878"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable The
<a name="line879"></a> *     iterable to filter.
<a name="line880"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} selectors An
<a name="line881"></a> *     iterable of items to be evaluated in a boolean context to determine if
<a name="line882"></a> *     the corresponding element in {@code iterable} should be included in the
<a name="line883"></a> *     result.
<a name="line884"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} A new iterator that returns the
<a name="line885"></a> *     filtered values.
<a name="line886"></a> * @template VALUE
<a name="line887"></a> */
<a name="line888"></a>goog.iter.compress = function(iterable, selectors) {
<a name="line889"></a>  var selectorIterator = goog.iter.toIterator(selectors);
<a name="line890"></a>
<a name="line891"></a>  return goog.iter.filter(iterable, function() {
<a name="line892"></a>    return !!selectorIterator.next();
<a name="line893"></a>  });
<a name="line894"></a>};
<a name="line895"></a>
<a name="line896"></a>
<a name="line897"></a>
<a name="line898"></a>/**
<a name="line899"></a> * Implements the {@code goog.iter.groupBy} iterator.
<a name="line900"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable The
<a name="line901"></a> *     iterable to group.
<a name="line902"></a> * @param {function(...[VALUE]): KEY=} opt_keyFunc  Optional function for
<a name="line903"></a> *     determining the key value for each group in the {@code iterable}. Default
<a name="line904"></a> *     is the identity function.
<a name="line905"></a> * @constructor
<a name="line906"></a> * @extends {goog.iter.Iterator.&lt;!Array&gt;}
<a name="line907"></a> * @template KEY, VALUE
<a name="line908"></a> * @private
<a name="line909"></a> */
<a name="line910"></a>goog.iter.GroupByIterator_ = function(iterable, opt_keyFunc) {
<a name="line911"></a>
<a name="line912"></a>  /**
<a name="line913"></a>   * The iterable to group, coerced to an iterator.
<a name="line914"></a>   * @type {!goog.iter.Iterator}
<a name="line915"></a>   */
<a name="line916"></a>  this.iterator = goog.iter.toIterator(iterable);
<a name="line917"></a>
<a name="line918"></a>  /**
<a name="line919"></a>   * A function for determining the key value for each element in the iterable.
<a name="line920"></a>   * If no function is provided, the identity function is used and returns the
<a name="line921"></a>   * element unchanged.
<a name="line922"></a>   * @type {function(...[VALUE]): KEY}
<a name="line923"></a>   */
<a name="line924"></a>  this.keyFunc = opt_keyFunc || goog.functions.identity;
<a name="line925"></a>
<a name="line926"></a>  /**
<a name="line927"></a>   * The target key for determining the start of a group.
<a name="line928"></a>   * @type {KEY}
<a name="line929"></a>   */
<a name="line930"></a>  this.targetKey;
<a name="line931"></a>
<a name="line932"></a>  /**
<a name="line933"></a>   * The current key visited during iteration.
<a name="line934"></a>   * @type {KEY}
<a name="line935"></a>   */
<a name="line936"></a>  this.currentKey;
<a name="line937"></a>
<a name="line938"></a>  /**
<a name="line939"></a>   * The current value being added to the group.
<a name="line940"></a>   * @type {VALUE}
<a name="line941"></a>   */
<a name="line942"></a>  this.currentValue;
<a name="line943"></a>};
<a name="line944"></a>goog.inherits(goog.iter.GroupByIterator_, goog.iter.Iterator);
<a name="line945"></a>
<a name="line946"></a>
<a name="line947"></a>/** @override */
<a name="line948"></a>goog.iter.GroupByIterator_.prototype.next = function() {
<a name="line949"></a>  while (this.currentKey == this.targetKey) {
<a name="line950"></a>    this.currentValue = this.iterator.next();  // Exits on StopIteration
<a name="line951"></a>    this.currentKey = this.keyFunc(this.currentValue);
<a name="line952"></a>  }
<a name="line953"></a>  this.targetKey = this.currentKey;
<a name="line954"></a>  return [this.currentKey, this.groupItems_(this.targetKey)];
<a name="line955"></a>};
<a name="line956"></a>
<a name="line957"></a>
<a name="line958"></a>/**
<a name="line959"></a> * Performs the grouping of objects using the given key.
<a name="line960"></a> * @param {KEY} targetKey  The target key object for the group.
<a name="line961"></a> * @return {!Array.&lt;VALUE&gt;} An array of grouped objects.
<a name="line962"></a> * @private
<a name="line963"></a> */
<a name="line964"></a>goog.iter.GroupByIterator_.prototype.groupItems_ = function(targetKey) {
<a name="line965"></a>  var arr = [];
<a name="line966"></a>  while (this.currentKey == targetKey) {
<a name="line967"></a>    arr.push(this.currentValue);
<a name="line968"></a>    try {
<a name="line969"></a>      this.currentValue = this.iterator.next();
<a name="line970"></a>    } catch (ex) {
<a name="line971"></a>      if (ex !== goog.iter.StopIteration) {
<a name="line972"></a>        throw ex;
<a name="line973"></a>      }
<a name="line974"></a>      break;
<a name="line975"></a>    }
<a name="line976"></a>    this.currentKey = this.keyFunc(this.currentValue);
<a name="line977"></a>  }
<a name="line978"></a>  return arr;
<a name="line979"></a>};
<a name="line980"></a>
<a name="line981"></a>
<a name="line982"></a>/**
<a name="line983"></a> * Creates an iterator that returns arrays containing elements from the
<a name="line984"></a> * {@code iterable} grouped by a key value. For iterables with repeated
<a name="line985"></a> * elements (i.e. sorted according to a particular key function), this function
<a name="line986"></a> * has a {@code uniq}-like effect. For example, grouping the array:
<a name="line987"></a> * {@code [A, B, B, C, C, A]} produces
<a name="line988"></a> * {@code [A, [A]], [B, [B, B]], [C, [C, C]], [A, [A]]}.
<a name="line989"></a> * @see http://docs.python.org/2/library/itertools.html#itertools.groupby
<a name="line990"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable The
<a name="line991"></a> *     iterable to group.
<a name="line992"></a> * @param {function(...[VALUE]): KEY=} opt_keyFunc  Optional function for
<a name="line993"></a> *     determining the key value for each group in the {@code iterable}. Default
<a name="line994"></a> *     is the identity function.
<a name="line995"></a> * @return {!goog.iter.Iterator.&lt;!Array&gt;} A new iterator that returns arrays of
<a name="line996"></a> *     consecutive key and groups.
<a name="line997"></a> * @template KEY, VALUE
<a name="line998"></a> */
<a name="line999"></a>goog.iter.groupBy = function(iterable, opt_keyFunc) {
<a name="line1000"></a>  return new goog.iter.GroupByIterator_(iterable, opt_keyFunc);
<a name="line1001"></a>};
<a name="line1002"></a>
<a name="line1003"></a>
<a name="line1004"></a>/**
<a name="line1005"></a> * Gives an iterator that gives the result of calling the given function
<a name="line1006"></a> * &lt;code&gt;f&lt;/code&gt; with the arguments taken from the next element from
<a name="line1007"></a> * &lt;code&gt;iterable&lt;/code&gt; (the elements are expected to also be iterables).
<a name="line1008"></a> *
<a name="line1009"></a> * Similar to {@see goog.iter#map} but allows the function to accept multiple
<a name="line1010"></a> * arguments from the iterable.
<a name="line1011"></a> *
<a name="line1012"></a> * @param {!goog.iter.Iterable.&lt;!goog.iter.Iterable&gt;} iterable The iterable of
<a name="line1013"></a> *     iterables to iterate over.
<a name="line1014"></a> * @param {function(this:THIS,...[*]):RESULT} f The function to call for every
<a name="line1015"></a> *     element.  This function takes N+2 arguments, where N represents the
<a name="line1016"></a> *     number of items from the next element of the iterable. The two
<a name="line1017"></a> *     additional arguments passed to the function are undefined and the
<a name="line1018"></a> *     iterator itself. The function should return a new value.
<a name="line1019"></a> * @param {THIS=} opt_obj The object to be used as the value of &#39;this&#39; within
<a name="line1020"></a> *     {@code f}.
<a name="line1021"></a> * @return {!goog.iter.Iterator.&lt;RESULT&gt;} A new iterator that returns the
<a name="line1022"></a> *     results of applying the function to each element in the original
<a name="line1023"></a> *     iterator.
<a name="line1024"></a> * @template THIS, RESULT
<a name="line1025"></a> */
<a name="line1026"></a>goog.iter.starMap = function(iterable, f, opt_obj) {
<a name="line1027"></a>  var iterator = goog.iter.toIterator(iterable);
<a name="line1028"></a>  var iter = new goog.iter.Iterator();
<a name="line1029"></a>
<a name="line1030"></a>  iter.next = function() {
<a name="line1031"></a>    var args = goog.iter.toArray(iterator.next());
<a name="line1032"></a>    return f.apply(opt_obj, goog.array.concat(args, undefined, iterator));
<a name="line1033"></a>  };
<a name="line1034"></a>
<a name="line1035"></a>  return iter;
<a name="line1036"></a>};
<a name="line1037"></a>
<a name="line1038"></a>
<a name="line1039"></a>/**
<a name="line1040"></a> * Returns an array of iterators each of which can iterate over the values in
<a name="line1041"></a> * {@code iterable} without advancing the others.
<a name="line1042"></a> * @see http://docs.python.org/2/library/itertools.html#itertools.tee
<a name="line1043"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable The
<a name="line1044"></a> *     iterable to tee.
<a name="line1045"></a> * @param {number=} opt_num  The number of iterators to create. Default is 2.
<a name="line1046"></a> * @return {!Array.&lt;goog.iter.Iterator.&lt;VALUE&gt;&gt;} An array of iterators.
<a name="line1047"></a> * @template VALUE
<a name="line1048"></a> */
<a name="line1049"></a>goog.iter.tee = function(iterable, opt_num) {
<a name="line1050"></a>  var iterator = goog.iter.toIterator(iterable);
<a name="line1051"></a>  var num = goog.isNumber(opt_num) ? opt_num : 2;
<a name="line1052"></a>  var buffers = goog.array.map(goog.array.range(num), function() {
<a name="line1053"></a>    return [];
<a name="line1054"></a>  });
<a name="line1055"></a>
<a name="line1056"></a>  var addNextIteratorValueToBuffers = function() {
<a name="line1057"></a>    var val = iterator.next();
<a name="line1058"></a>    goog.array.forEach(buffers, function(buffer) {
<a name="line1059"></a>      buffer.push(val);
<a name="line1060"></a>    });
<a name="line1061"></a>  };
<a name="line1062"></a>
<a name="line1063"></a>  var createIterator = function(buffer) {
<a name="line1064"></a>    // Each tee&#39;d iterator has an associated buffer (initially empty). When a
<a name="line1065"></a>    // tee&#39;d iterator&#39;s buffer is empty, it calls
<a name="line1066"></a>    // addNextIteratorValueToBuffers(), adding the next value to all tee&#39;d
<a name="line1067"></a>    // iterators&#39; buffers, and then returns that value. This allows each
<a name="line1068"></a>    // iterator to be advanced independently.
<a name="line1069"></a>    var iter = new goog.iter.Iterator();
<a name="line1070"></a>
<a name="line1071"></a>    iter.next = function() {
<a name="line1072"></a>      if (goog.array.isEmpty(buffer)) {
<a name="line1073"></a>        addNextIteratorValueToBuffers();
<a name="line1074"></a>      }
<a name="line1075"></a>      goog.asserts.assert(!goog.array.isEmpty(buffer));
<a name="line1076"></a>      return buffer.shift();
<a name="line1077"></a>    };
<a name="line1078"></a>
<a name="line1079"></a>    return iter;
<a name="line1080"></a>  };
<a name="line1081"></a>
<a name="line1082"></a>  return goog.array.map(buffers, createIterator);
<a name="line1083"></a>};
<a name="line1084"></a>
<a name="line1085"></a>
<a name="line1086"></a>/**
<a name="line1087"></a> * Creates an iterator that returns arrays containing a count and an element
<a name="line1088"></a> * obtained from the given {@code iterable}.
<a name="line1089"></a> * @see http://docs.python.org/2/library/functions.html#enumerate
<a name="line1090"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable The
<a name="line1091"></a> *     iterable to enumerate.
<a name="line1092"></a> * @param {number=} opt_start  Optional starting value. Default is 0.
<a name="line1093"></a> * @return {!goog.iter.Iterator.&lt;!Array&gt;} A new iterator containing count/item
<a name="line1094"></a> *     pairs.
<a name="line1095"></a> * @template VALUE
<a name="line1096"></a> */
<a name="line1097"></a>goog.iter.enumerate = function(iterable, opt_start) {
<a name="line1098"></a>  return goog.iter.zip(goog.iter.count(opt_start), iterable);
<a name="line1099"></a>};
<a name="line1100"></a>
<a name="line1101"></a>
<a name="line1102"></a>/**
<a name="line1103"></a> * Creates an iterator that returns the first {@code limitSize} elements from an
<a name="line1104"></a> * iterable. If this number is greater than the number of elements in the
<a name="line1105"></a> * iterable, all the elements are returned.
<a name="line1106"></a> * @see http://goo.gl/V0sihp Inspired by the limit iterator in Guava.
<a name="line1107"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable The
<a name="line1108"></a> *     iterable to limit.
<a name="line1109"></a> * @param {number} limitSize  The maximum number of elements to return.
<a name="line1110"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} A new iterator containing
<a name="line1111"></a> *     {@code limitSize} elements.
<a name="line1112"></a> * @template VALUE
<a name="line1113"></a> */
<a name="line1114"></a>goog.iter.limit = function(iterable, limitSize) {
<a name="line1115"></a>  goog.asserts.assert(goog.math.isInt(limitSize) &amp;&amp; limitSize &gt;= 0);
<a name="line1116"></a>
<a name="line1117"></a>  var iterator = goog.iter.toIterator(iterable);
<a name="line1118"></a>
<a name="line1119"></a>  var iter = new goog.iter.Iterator();
<a name="line1120"></a>  var remaining = limitSize;
<a name="line1121"></a>
<a name="line1122"></a>  iter.next = function() {
<a name="line1123"></a>    if (remaining-- &gt; 0) {
<a name="line1124"></a>      return iterator.next();
<a name="line1125"></a>    }
<a name="line1126"></a>    throw goog.iter.StopIteration;
<a name="line1127"></a>  };
<a name="line1128"></a>
<a name="line1129"></a>  return iter;
<a name="line1130"></a>};
<a name="line1131"></a>
<a name="line1132"></a>
<a name="line1133"></a>/**
<a name="line1134"></a> * Creates an iterator that is advanced {@code count} steps ahead. Consumed
<a name="line1135"></a> * values are silently discarded. If {@code count} is greater than the number
<a name="line1136"></a> * of elements in {@code iterable}, an empty iterator is returned. Subsequent
<a name="line1137"></a> * calls to {@code next()} will throw {@code goog.iter.StopIteration}.
<a name="line1138"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable The
<a name="line1139"></a> *     iterable to consume.
<a name="line1140"></a> * @param {number} count  The number of elements to consume from the iterator.
<a name="line1141"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} An iterator advanced zero or more steps
<a name="line1142"></a> *     ahead.
<a name="line1143"></a> * @template VALUE
<a name="line1144"></a> */
<a name="line1145"></a>goog.iter.consume = function(iterable, count) {
<a name="line1146"></a>  goog.asserts.assert(goog.math.isInt(count) &amp;&amp; count &gt;= 0);
<a name="line1147"></a>
<a name="line1148"></a>  var iterator = goog.iter.toIterator(iterable);
<a name="line1149"></a>
<a name="line1150"></a>  while (count-- &gt; 0) {
<a name="line1151"></a>    goog.iter.nextOrValue(iterator, null);
<a name="line1152"></a>  }
<a name="line1153"></a>
<a name="line1154"></a>  return iterator;
<a name="line1155"></a>};
<a name="line1156"></a>
<a name="line1157"></a>
<a name="line1158"></a>/**
<a name="line1159"></a> * Creates an iterator that returns a range of elements from an iterable.
<a name="line1160"></a> * Similar to {@see goog.array#slice} but does not support negative indexes.
<a name="line1161"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable The
<a name="line1162"></a> *     iterable to slice.
<a name="line1163"></a> * @param {number} start  The index of the first element to return.
<a name="line1164"></a> * @param {number=} opt_end  The index after the last element to return. If
<a name="line1165"></a> *     defined, must be greater than or equal to {@code start}.
<a name="line1166"></a> * @return {!goog.iter.Iterator.&lt;VALUE&gt;} A new iterator containing a slice of
<a name="line1167"></a> *     the original.
<a name="line1168"></a> * @template VALUE
<a name="line1169"></a> */
<a name="line1170"></a>goog.iter.slice = function(iterable, start, opt_end) {
<a name="line1171"></a>  goog.asserts.assert(goog.math.isInt(start) &amp;&amp; start &gt;= 0);
<a name="line1172"></a>
<a name="line1173"></a>  var iterator = goog.iter.consume(iterable, start);
<a name="line1174"></a>
<a name="line1175"></a>  if (goog.isNumber(opt_end)) {
<a name="line1176"></a>    goog.asserts.assert(
<a name="line1177"></a>        goog.math.isInt(/** @type {number} */ (opt_end)) &amp;&amp; opt_end &gt;= start);
<a name="line1178"></a>    iterator = goog.iter.limit(iterator, opt_end - start /* limitSize */);
<a name="line1179"></a>  }
<a name="line1180"></a>
<a name="line1181"></a>  return iterator;
<a name="line1182"></a>};
<a name="line1183"></a>
<a name="line1184"></a>
<a name="line1185"></a>/**
<a name="line1186"></a> * Checks an array for duplicate elements.
<a name="line1187"></a> * @param {Array.&lt;VALUE&gt;|goog.array.ArrayLike} arr The array to check for
<a name="line1188"></a> *     duplicates.
<a name="line1189"></a> * @return {boolean} True, if the array contains duplicates, false otherwise.
<a name="line1190"></a> * @private
<a name="line1191"></a> * @template VALUE
<a name="line1192"></a> */
<a name="line1193"></a>// TODO(user): Consider moving this into goog.array as a public function.
<a name="line1194"></a>goog.iter.hasDuplicates_ = function(arr) {
<a name="line1195"></a>  var deduped = [];
<a name="line1196"></a>  goog.array.removeDuplicates(arr, deduped);
<a name="line1197"></a>  return arr.length != deduped.length;
<a name="line1198"></a>};
<a name="line1199"></a>
<a name="line1200"></a>
<a name="line1201"></a>/**
<a name="line1202"></a> * Creates an iterator that returns permutations of elements in
<a name="line1203"></a> * {@code iterable}.
<a name="line1204"></a> *
<a name="line1205"></a> * Permutations are obtained by taking the Cartesian product of
<a name="line1206"></a> * {@code opt_length} iterables and filtering out those with repeated
<a name="line1207"></a> * elements. For example, the permutations of {@code [1,2,3]} are
<a name="line1208"></a> * {@code [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]}.
<a name="line1209"></a> * @see http://docs.python.org/2/library/itertools.html#itertools.permutations
<a name="line1210"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable The
<a name="line1211"></a> *     iterable from which to generate permutations.
<a name="line1212"></a> * @param {number=} opt_length Length of each permutation. If omitted, defaults
<a name="line1213"></a> *     to the length of {@code iterable}.
<a name="line1214"></a> * @return {!goog.iter.Iterator.&lt;!Array.&lt;VALUE&gt;&gt;} A new iterator containing the
<a name="line1215"></a> *     permutations of {@code iterable}.
<a name="line1216"></a> * @template VALUE
<a name="line1217"></a> */
<a name="line1218"></a>goog.iter.permutations = function(iterable, opt_length) {
<a name="line1219"></a>  var elements = goog.iter.toArray(iterable);
<a name="line1220"></a>  var length = goog.isNumber(opt_length) ? opt_length : elements.length;
<a name="line1221"></a>
<a name="line1222"></a>  var sets = goog.array.repeat(elements, length);
<a name="line1223"></a>  var product = goog.iter.product.apply(undefined, sets);
<a name="line1224"></a>
<a name="line1225"></a>  return goog.iter.filter(product, function(arr) {
<a name="line1226"></a>    return !goog.iter.hasDuplicates_(arr);
<a name="line1227"></a>  });
<a name="line1228"></a>};
<a name="line1229"></a>
<a name="line1230"></a>
<a name="line1231"></a>/**
<a name="line1232"></a> * Creates an iterator that returns combinations of elements from
<a name="line1233"></a> * {@code iterable}.
<a name="line1234"></a> *
<a name="line1235"></a> * Combinations are obtained by taking the {@see goog.iter#permutations} of
<a name="line1236"></a> * {@code iterable} and filtering those whose elements appear in the order they
<a name="line1237"></a> * are encountered in {@code iterable}. For example, the 3-length combinations
<a name="line1238"></a> * of {@code [0,1,2,3]} are {@code [[0,1,2], [0,1,3], [0,2,3], [1,2,3]]}.
<a name="line1239"></a> * @see http://docs.python.org/2/library/itertools.html#itertools.combinations
<a name="line1240"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable The
<a name="line1241"></a> *     iterable from which to generate combinations.
<a name="line1242"></a> * @param {number} length The length of each combination.
<a name="line1243"></a> * @return {!goog.iter.Iterator.&lt;!Array.&lt;VALUE&gt;&gt;} A new iterator containing
<a name="line1244"></a> *     combinations from the {@code iterable}.
<a name="line1245"></a> * @template VALUE
<a name="line1246"></a> */
<a name="line1247"></a>goog.iter.combinations = function(iterable, length) {
<a name="line1248"></a>  var elements = goog.iter.toArray(iterable);
<a name="line1249"></a>  var indexes = goog.iter.range(elements.length);
<a name="line1250"></a>  var indexIterator = goog.iter.permutations(indexes, length);
<a name="line1251"></a>  // sortedIndexIterator will now give arrays of with the given length that
<a name="line1252"></a>  // indicate what indexes into &quot;elements&quot; should be returned on each iteration.
<a name="line1253"></a>  var sortedIndexIterator = goog.iter.filter(indexIterator, function(arr) {
<a name="line1254"></a>    return goog.array.isSorted(arr);
<a name="line1255"></a>  });
<a name="line1256"></a>
<a name="line1257"></a>  var iter = new goog.iter.Iterator();
<a name="line1258"></a>
<a name="line1259"></a>  function getIndexFromElements(index) {
<a name="line1260"></a>    return elements[index];
<a name="line1261"></a>  }
<a name="line1262"></a>
<a name="line1263"></a>  iter.next = function() {
<a name="line1264"></a>    return goog.array.map(
<a name="line1265"></a>        /** @type {!Array.&lt;number&gt;} */
<a name="line1266"></a>        (sortedIndexIterator.next()), getIndexFromElements);
<a name="line1267"></a>  };
<a name="line1268"></a>
<a name="line1269"></a>  return iter;
<a name="line1270"></a>};
<a name="line1271"></a>
<a name="line1272"></a>
<a name="line1273"></a>/**
<a name="line1274"></a> * Creates an iterator that returns combinations of elements from
<a name="line1275"></a> * {@code iterable}, with repeated elements possible.
<a name="line1276"></a> *
<a name="line1277"></a> * Combinations are obtained by taking the Cartesian product of {@code length}
<a name="line1278"></a> * iterables and filtering those whose elements appear in the order they are
<a name="line1279"></a> * encountered in {@code iterable}. For example, the 2-length combinations of
<a name="line1280"></a> * {@code [1,2,3]} are {@code [[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]]}.
<a name="line1281"></a> * @see http://docs.python.org/2/library/itertools.html#itertools.combinations_with_replacement
<a name="line1282"></a> * @see http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition
<a name="line1283"></a> * @param {!goog.iter.Iterator.&lt;VALUE&gt;|!goog.iter.Iterable} iterable The
<a name="line1284"></a> *     iterable to combine.
<a name="line1285"></a> * @param {number} length The length of each combination.
<a name="line1286"></a> * @return {!goog.iter.Iterator.&lt;!Array.&lt;VALUE&gt;&gt;} A new iterator containing
<a name="line1287"></a> *     combinations from the {@code iterable}.
<a name="line1288"></a> * @template VALUE
<a name="line1289"></a> */
<a name="line1290"></a>goog.iter.combinationsWithReplacement = function(iterable, length) {
<a name="line1291"></a>  var elements = goog.iter.toArray(iterable);
<a name="line1292"></a>  var indexes = goog.array.range(elements.length);
<a name="line1293"></a>  var sets = goog.array.repeat(indexes, length);
<a name="line1294"></a>  var indexIterator = goog.iter.product.apply(undefined, sets);
<a name="line1295"></a>  // sortedIndexIterator will now give arrays of with the given length that
<a name="line1296"></a>  // indicate what indexes into &quot;elements&quot; should be returned on each iteration.
<a name="line1297"></a>  var sortedIndexIterator = goog.iter.filter(indexIterator, function(arr) {
<a name="line1298"></a>    return goog.array.isSorted(arr);
<a name="line1299"></a>  });
<a name="line1300"></a>
<a name="line1301"></a>  var iter = new goog.iter.Iterator();
<a name="line1302"></a>
<a name="line1303"></a>  function getIndexFromElements(index) {
<a name="line1304"></a>    return elements[index];
<a name="line1305"></a>  }
<a name="line1306"></a>
<a name="line1307"></a>  iter.next = function() {
<a name="line1308"></a>    return goog.array.map(
<a name="line1309"></a>        /** @type {!Array.&lt;number&gt;} */
<a name="line1310"></a>        (sortedIndexIterator.next()), getIndexFromElements);
<a name="line1311"></a>  };
<a name="line1312"></a>
<a name="line1313"></a>  return iter;
<a name="line1314"></a>};
</pre>


</body>
</html>
